In recent years, the importance of information security technologies has been increasing. Moreover, public-key cryptography has been actively studied as one of fundamental techniques of information security.
Public-key cryptography includes several types. Algorithms such as Rivest, Shamir, Adleman (RSA), and Diffie-Hellman (DH), which use a modular exponentiation computation, elliptical curve cryptography (ECC) using a scalar multiplication of a point on an elliptic curve, and the like are known.
In use of public-key cryptography, it is important to keep a private key secret in order to retain security. In recent years, however, several attack methods for decrypting (or breaking) a private key have been known. Accordingly, for tamper-proofness of a device for executing a process using public-key cryptography, the device needs to take at least measures against known attack methods.
For example, an attack method called a power analysis (PA) attack is known as one type of side-channel attacks. Moreover, PAs include two types such as a simple power analysis (SPA) and a differential power analysis (DPA).
Accordingly, for a device that executes a process using public-key cryptography, safety from SPA attacks and safety from DPA attacks are demanded. For example, an A&D-always method is one of measures against SPA attacks, whereas a method for randomizing data is one type of measures against DPA attacks.
Conventionally, it was considered that devices were safe from both of SPAs and DPAs by combining an SPA measure implemented with the A&D-always method and a DPA measure implemented with the randomizing method, thereby making it possible to completely prevent power analyses.
However, the inventor devised an attack method that can decrypt a value of a private key d by using a power waveform even if these measures are taken. This attack is referred to as a “special PA” in this application.
Initially, the inventor found out that the following attack can be conducted as a special PA when the private key d is not randomized. Namely, it was proved that an attacker can decrypt two-thirds of all bit values of the private key d with a special PA using a selected message pair of P and Q that satisfy P3=Q3 (mod n) and P≠Q for a device having a modular exponentiation function. Also for a device having a scalar multiplication function of a point, it was proved that an attacker can decrypt two-thirds of all the bit values of the private key d by conducting a similar attack with a special PA using a selected message pair of P and Q that satisfy 3P=3Q and P≠Q. Moreover, it was proved that this attack can be expanded to a special PA using a selected message pair of P and Q that satisfy Pα=Qα(mod n) and P≠Q (or αP=αQ and P≠Q) for a prime number α equal to or larger than 3.
Next, the inventor found out that the following attack can be conducted as a special PA used when a private key d is randomized. Namely, randomized exponents are made to match so that randomized private keys become identical in a case where P is input and in a case where Q is input, whereby an attack method similar to that in the case where the private key is not randomized can be applied. The simplest way to implement this is to repeat a power measurement when Q is given by a plurality of times until a randomized key in a case where P is given and that in a case where Q is given match. Although the length of time needed for this power measurement is not short at all, it was proved that the power measurement needed to successfully conduct the attack can be completed within a sufficiently realistic time frame. For the power measurement, the length of time in units of seconds proportional to the number of times that the power measurement is made is demanded due to a computation process and a communication time of a low-speed device such as a smart card or the like. However, once the power measurement has been completed and data of the power measurement has been transferred to a PC, the high-performance PC can analyze the data at high speed.